//#include <stdio.h>
//
//int main()
//{
//    int n = 0;
//    scanf("%d",&n);
//    char str[n];
//    if(n < 3)
//    {
//        printf("0\n");
//        return 0;
//    }
//    scanf("%s",str);
//    char *prev = str;
//    int sum = 0;
//    while(*prev)
//    {
//        char *cur = prev + 1;
//        while(*cur)
//        {
//            char *next = cur + 1;
//            while(*next)
//            {
//                if(*prev != *cur && *cur == *next)
//                {
//                    ++sum;
//                }#include <stdio.h>
//
//                  int main()
//                {
//                    int n = 0;
//                    scanf("%d",&n);
//                    char str[n];
//                    if(n < 3)
//                    {
//                        printf("0\n");
//                        return 0;
//                    }
//                    scanf("%s",str);
//                    char *prev = str;
//                    int sum = 0;
//                    while(*prev)
//                    {
//                        char *cur = prev + 1;
//                        while(*cur)
//                        {
//                            char *next = cur + 1;
//                            while(*next)
//                            {
//                                if(*prev != *cur && *cur == *next)
//                                {
//                                    ++sum;
//                                }
//                                ++next;
//                            }
//                            ++cur;
//                        }
//                        ++prev;
//                    }
//                    printf("%d\n",sum);
//                    return 0;
//                }
//                ++next;
//            }
//            ++cur;
//        }
//        ++prev;
//    }
//    printf("%d\n",sum);
//    return 0;
//}
//#include "test.h"
//2023.11.14
//using namespace std;
//class Date
//{
//public:
//
//private:
//
//};
//int main()
//{
//
//    return 0;
//}
//using namespace std;
//inline int Add(int x, int y)
//{
//    return x + y;
//}
//inline int Add(char x, int y)
//{
//    1;
//    1;
//    1;
//    int c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//    c = x + y;
//
//
//    return x + y;
//}
//char Add(char x, char y)
//{
//    return x + y;
//}
//int main()
//{
//    Add(1,2);
//    Add('w',2);
//    Add('1','2');
//    return 0;
//}
//using namespace std;
//typedef char* pstring;
//int main()
//{
//    const pstring p1 = nullptr;
//    const pstring* p2;
//    cout << typeid(p1).name() << endl;
//    cout << typeid(p2).name() << endl;
//    return 0;
//}
//using namespace std;
//int main()
//{
//    int a[] = {1,2,3};
//    for(auto m:a)
//    {
//        cout << m << ' ';
//    }
//    cout << endl;
//    return 0;
//}
//using std::cout;
//using std::endl;
//class Stack
//{
//public:
//    Stack()
//    {
//        _a = nullptr;
//        _size = 0;
//        _capacity = 0;
//    }
//    void Creat()
//    {
//        int new_capacity = _capacity==0 ? 4 : _capacity*2;
//        int *room = (int*)realloc(_a,sizeof(int)*new_capacity);
//        if(room == nullptr)
//        {
//            perror("realloc fail");
//            exit(-1);
//        }
//        _a = room;
//        _capacity = new_capacity;
//    }
//    void Push(int num)
//    {
//        if(_size == _capacity)
//        {
//            Creat();
//        }
//        _a[_size++] = num;
//    }
//    ~Stack()
//    {
//        free(_a);
//
//    }
//private:
//    int *_a;
//    int _size;
//    int _capacity;
//};
//int main()
//{
//    Stack st;
//    st.Push(3);
//    st.Push(3);
//    st.Push(3);
//    st.Push(3);
//    st.Push(3);
//    return 0;
//}
//int main()
//{
//    Date date(2023,11,14);
//    date.Print();
//    return 0;
//}
//using namespace std;
//class Date
//{
//public:
//    ~Date()
//    {
//        cout << "~Date" << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//Date a;
//int main()
//{
//    Date b;
//     Date c;
//    return 0;
////}
//using namespace std;
//class A
//{
//public:
//    void Printf()
//    {
//        cout << _a << endl;
//    }
//private:
//    int _a;
//};
//int main()
//{
//    A *a = nullptr;
//    a->Printf();
//    return 0;
//}
//}
//using namespace std;
//class Date
//{
//public:
//    void Init(int _year, int _month, int _day)
//    {
//        _year = _year;
//        _month = _month;
//        _day = _day;
//    }
//    void Printf()
//    {
//        cout << _year << '-' << _month << '-' << _day << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date;
//    date.Init(2023,11,14);
//    date.Printf();
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year, int month, int day)
//    {
//        _year = year;
//        _month = month;
//        _day = day;
//    }
//    void Printf()
//    {
//        cout << _year << '-' << _month << '-' << _day << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date1(2023,11,14);
//    date1.Printf();
//    Date date2(2022,11,14);
//    date2.Printf();
//    return 0;
//}
//#include <stdio.h>
//typedef struct Date
//{
//    int _year;
//    int _month;
//    int _day;
//}Date;
//void Init(Date *pd,int year, int month, int day)
//{
//    pd->_year = year;
//    pd->_month = month;
//    pd->_day = day;
//}
//void Print(Date *pd)
//{
//    printf("%d-%d-%d\n",pd->_year,pd->_month,pd->_day);
//}
//int main()
//{
//    Date date1;
//    Init(&date1,2023,11,14);
//    Print(&date1);
//
//    Date date2;
//    Init(&date2,2022,11,14);
//    Print(&date2);
//    return 0;
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year, int month, int day)
//    {
//       this-> _year = year;
//       this->_month = month;
//       this-> _day = day;
//    }
//    void Printf()
//    {
//        cout << this-> _year << '-' << this-> _month << '-' << this-> _day << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date1(2023,11,14);
//    date1.Printf();
//    Date date2(2022,11,14);
//    date2.Printf();
//    return 0;
//}
//#include <iostream>
//using namespace std;
//// 1.下面程序编译运行结果是？ A、编译报错 B、运行崩溃 C、正常运行
//class A
//{
//public:
//    void Print()
//    {
//        cout << "Print()" << endl;
//    }
//private:
//    int _a;
//};
//int main()
//{
//    A* p = nullptr;
//    p->Print();
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year, int month, int day)
//    {
//        _year = year;
//        _month = month;
//        _day = day;
//    }
//    static void Change(int year)
//    {
//        _year = year;
//    }
//    void Printf()
//    {
//        cout << _year << '-' << _month << '-' << _day << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date1(2023,11,14);
//    date1.Printf();
//    Date date2(2022,11,14);
//    date2.Printf();
//    return 0;
//}
//#include <iostream>
//using std::cout;
//using std::endl;
//class Date
//{
//public:
////    Date()
////    {
////        _year = 2023;
////        _month = 11;
////        _day = 14;
////    }
//    void Print()
//    {
//        cout << _year << '-' << _month << '-' << _day << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date;
//    date.Print();
//}
//#include <iostream>
//using std::cout;
//using std::endl;
//class Date
//{
//public:
//    Date()
//    {
//        _year = 2023;
//        _month = 11;
//        _day = 14;
//    }
//    void Print()
//    {
//        cout << _year << '-' << _month << '-' << _day << endl;
//    }
//private:
//    int _year = 2022;
//    int _month = 11;
//    int _day = 14;
//};
//int main()
//{
//    Date date;
//    date.Print();
//}
//#include "test.h"
//using std::cout;
//using std::endl;
//
//int main()
//{
////    MyQueue mq(1);
////    Stack st;
//    return 0;
//}
//////////////////////////2023.11.15
//#include <iostream>
//using namespace std;
//
//int main()
//{
//    return 0;
//}
//
//#include "test.h"
//using std::cout;
//using std::endl;
//
//int main()
//{
////    MyQueue mq(1);
//    Stack st;
//    st.Push(2);
//    st.Push(3);
//    st.Push(4);
//    st.Push(5);
//    st.Push(6);
//    st.Print();
//
//    Stack st2(st);
//    st2.Print();
//    return 0;
//}
/*
 * //
// Created by 王有东 on 2023/11/9.
//

//#include "test.h"
//void Stack:: Init()
//{
//    a = nullptr;
//    val = 0;
//    capacity = 0;
//}
//void Stack::Push(int num)
//{
//    ///////
//}
//void Date::Assign(int year)
//{
//    year = year;
//}
//void Date::Printf()
//{
//    cout << _year << "-" << _month << "-" << _day << endl;
//}
//Date::Date(int year, int month, int day)
//{
//    _year = year;
//    _month = month;
//    _day = day;
//}
//
//void Date::Print()
//{
//    cout << _year << '-' << _month << '-' << _day << endl;
//}
//#include "test.h"
//Stack::Stack()
//{
//    _a = (int*)malloc(sizeof(int) * 4);
//    if(_a == nullptr)
//    {
//        perror("malloc fail");
//        exit(-1);
//    }
//    _size = 0;
//    _capacity = 4;
//}
//Stack::Stack(const Stack &new_st)
//{
//    _a = (int*) malloc(sizeof(int) * (new_st._capacity));
//    if(_a == nullptr)
//    {
//        perror("Stack(Stack &new_st) malloc fail");
//        exit(-1);
//    }
//    memcpy(_a,new_st._a,sizeof(int)*new_st._size);
//
//    _size = new_st._size;
//    _capacity = new_st._capacity;
//}
//void Stack:: Create()
//{
//    int *tmp = (int*) realloc(_a,sizeof(int) * _capacity*2);
//    if(tmp == nullptr)
//    {
//        perror("malloc fail");
//        exit(-1);
//    }
//    _a = tmp;
//    _capacity = _capacity*2;
//}
//void Stack::Push(int num)
//{
//    if(_capacity == _size)
//        Create();
//    _a[_size++] = num;
//}
//void Stack::Print()
//{
//    for (int i = 0; i < _size; ++i)
//    {
//        cout << _a[i] << ' ';
//    }
//    cout << endl;
//}
//Stack::~Stack()
//{
//    free(_a);
//    _capacity = 0;
//    _size = 0;
//    _a = nullptr;
//}
////MyQueue::MyQueue(int a)
////{
////    a = 0;
////}/
 */
//#include "test.h"
//void Test1()
//{
//    Date date1(2006,9,16);
//    Date date2(2006,4,16);
//    if(date1 > date2)
//        cout << "date1 > date2" << endl;
//    if(date1 < date2)
//        cout << "date1 < date2" << endl;
//    if(date1 <= date2)
//        cout << "date1 <= date2" << endl;
//    if(date1 >= date2)
//        cout << "date1 >= date2" << endl;
//    if(date1 != date2)
//        cout << "date1 != date2" << endl;
//    if(date1 == date2)
//        cout << "date1 == date2" << endl;
//
//    Date date3 = date1;
//    date1.Print();
//    date3.Print();
//}
//void Test2()
//{
//    Date date2(2023,11,15);
//    Date date1(1996,6,29);
//    date2.Print();
//    Date date3 = date2 - 100;
//    date3.Print();
//    Date date4 = date2 - 10000;
//    date4.Print();
//    Date date5 = date2 + 100;
//    date5.Print();
//    Date date6 = date1 + 10000;
//    date6.Print();
//
//
//}
//void Test3()
//{
//    Date date1(2022,6,29);
//    Date date2;
//    date2 = date1;
//    date1.Print();
//    date2.Print();
//}
//int main()
//{
//    Test1(); //> < = ≤ ≥ != =
//    Test2();//日期+，+=，-，-=，-日期
////    Test3();//++，--
//    return 0;
//}
/*

//全缺省的构造函数
Date::Date(int year, int month, int day)
{
    assert(year >= 1 && month >= 1 || month <= 12 || day >= 1 && day <= GetMonthDay(year,month));
    _year = year;
    _month = month;
    _day = day;
}

//拷贝构造函数
Date::Date(const Date &new_date)
{
    _year = new_date._year;
    _month = new_date._month;
    _day = new_date._day;
}

//析构函数
Date::~Date()
{
    _year = 0;
    _month = 0;
    _day = 0;
}

//打印日期
void Date::Print()
{
    cout << _year << '-' << _month << '-' << _day << endl;
}

//赋值运算符重载 =
//写返回值是为了连续赋值
Date& Date::operator=(const Date& another)
{
    if(this != &another)
    {
        _year = another._year;
        _month = another._month;
        _day = another._day;
    }
    return *this;
}



//运算符重载 ==
bool Date::operator==(const Date& another)
{
    return _year == another._year && _month == another._month && _day == another._day;
}
//运算符重载 !=
bool Date::operator!=(const Date& another)
{
    return !(*this == another);
}

//运算符重载 >
bool Date::operator>(const Date& another)
{
    if(_year > another._year)
    {
        return true;
    }
    else if(_year == another._year && _month > another._month)
    {
        return true;
    }
    else if(_year == another._year && _month == another._month && _day > another._day)
    {
        return true;
    }
    return false;
}

//运算符重载 >=
bool Date::operator>=(const Date& another)
{
    return *this > another || *this == another;
}

//运算符重载 <
bool Date::operator<(const Date& another)
{
    return !(*this >= another);
}

//运算符重载 <=
bool Date::operator<=(const Date& another)
{
    return !(*this > another);
}


//获取某年某月的天数
int Date::GetMonthDay(int year, int month)
{
    assert(year >= 1 && month >= 1 && month <= 12);

    int day[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    if(month == 2 && ((year%4 == 0 && year%100 != 0) || (year%400 == 0)))
        return 29;
    return day[month];
}
//日期+=天数
Date& Date::operator+=(int day)
{
    if(day < 0)
    {
        return *this -= -day;
    }

    _day += day;
    while(_day > GetMonthDay(_year,_month))
    {
        _day -= GetMonthDay(_year,_month);
        _month++;

        if(_month == 13)
        {
            _year++;
            _month = 1;
        }
    }
    return *this;
}

//日期+天数
Date Date::operator+(int day)
{
    Date date(*this);
    date += day;
    return date;
}

//日期-=天数
Date& Date::operator-=(int day)
{
    if(day < 0)
    {
        return *this += -day;
    }

    _day -= day;
    while(_day <= 0)
    {
        --_month;
        if(_month == 0)
        {
            --_year;
            _month = 12;
        }
        _day += GetMonthDay(_year,_month);
    }


    assert(_year > 0 && _month > 0 && _month < 13 && _day <= GetMonthDay(_year,_month));

    return *this;
}

//日期-天数
Date Date::operator-(int day)
{
    Date date(*this);
    date -= day;

    return date;
}

int GetYearDay(int year)
{
    if( (year%4 == 0 && year%100 != 0) || year%400 == 0)
        return 366;
    else
        return 365;
}
//日期-日期（简单但相对低效）
int Date::operator-(const Date& another)
{
    Date max = *this;
    Date min = another;
    int flag = 1;
    int dif = 0;

    if(*this < another)
    {
        max = another;
        min = *this;
        flag = -1;
    }

    while(min < max)
    {
        ++dif;
        ++min;
    }

    dif *= flag;
    return dif;
}
//日期-日期（麻烦但高效）
//int Date::operator-(const Date& another)
//{
//    assert(*this > another);
//
//    Date big_date(*this);
//    Date small_date(another);
//    ////////////////////////////////////////
//    int big_day = 0;
//    int big_year = big_date._year - 1;
//    while (big_year >= small_date._year)
//    {
//        big_day += GetYearDay(big_year);
//        big_year--;
//    }
//
//    big_date._month--;
//    while(big_date._month != 0)
//    {
//        big_day += GetMonthDay(big_date._year,big_date._month);
//        big_date._month--;
//    }
//
//    big_day += big_date._day;
//    ////////////////////////////////////////
//    int small_day = 0;
//    small_date._month--;
//    while(small_date._month != 0)
//    {
//        small_day += GetMonthDay(small_date._year,small_date._month);
//        small_date._month--;
//    }
//
//    small_day += small_date._day;
//    ////////////////////////////////////////
//    return big_day - small_day;
//}

//前置++
Date& Date::operator++()
{
    *this += 1;
    return *this;
}

//后置++
Date Date::operator++(int)
{
    Date tmp(*this);
    *this += 1;
    return tmp;
}

//前置--
Date& Date::operator--()
{
    *this -= 1;
    return *this;
}
//后置--
Date Date::operator--(int)
{
    Date tmp(*this);
    *this -= 1;
    return tmp;
}/
 class Date
{
public:
    //全缺省的构造函数
    Date(int year = 2003, int month = 11, int day = 15);
    //拷贝构造函数
    Date(const Date& new_date);
    //析构函数
    ~Date();
    //赋值运算符重载
    Date& operator=(const Date& another);

    //打印日期
    void Print();
    //获取某年某月的天数
    int GetMonthDay(int year, int month);

    //运算符重载 >
    bool operator>(const Date& another);
    //运算符重载 ==
    bool operator==(const Date& another);
    //运算符重载 <
    bool operator<(const Date& another);
    //运算符重载 >=
    bool operator>=(const Date& another);
    //运算符重载 <=
    bool operator<=(const Date& another);
    //运算符重载 !=
    bool operator!=(const Date& another);

    //日期+天数
    Date operator+(int day);
    //日期+=天数
    Date& operator+=(int day);
    //日期-=天数
    Date& operator-=(int day);
    //日期-天数
    Date operator-(int day);
    //日期-日期
    int operator-(const Date& another);

    //前置++
    Date& operator++();
    //后置++
    Date operator++(int);
    //前置--
    Date& operator--();
    //后置--
    Date operator--(int);

private:
    int _year;
    int _month;
    int _day;
};
 //using namespace std;
//inline int Add(int x,int y)
//{
//    return x + y;
//}


//class Stack
//{
//private:
//    int val;
//    int capacity;
//    int* a;
//public:
//    void Init();
//    void Push(int num);
//};
//class Date
//{
//public:
//    int _year;
//    int _month;
//    int _day;
//
//    void Printf();
//};
//inline void Add(double x,double y)
//{
//    cout << x + y << endl;
//}
//class Date
//{
//public:
//    Date(int year, int month, int day); //初始化
//    void Print();
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//class Stack
//{
//public:
//    Stack();
//    Stack(const Stack &new_st);
//    void Create();
//    void Push(int num);
//    void Print();
//    ~Stack();
//private:
//    int *_a;
//    int _size;
//    int _capacity;
//};
//class MyQueue
//{
//public:
//    MyQueue(int a);
//private:
//    Stack st1;
//    Stack st2;
//    int a;
//};
 */
//#include "test.h"
//void Test1()
//{
//    Date today(2023, 2, 28);
//    Date yesterday(2023,2,28);
//    if(today > yesterday)
//        cout << "today > yesterday" << endl;
//    if(today < yesterday)
//        cout << "today < yesterday" << endl;
//    if(today == yesterday)
//        cout << "today == yesterday" << endl;
//    if(today <= yesterday)
//        cout << "today <= yesterday" << endl;
//    if(today >= yesterday)
//        cout << "today >= yesterday" << endl;
//    if(today != yesterday)
//        cout << "today != yesterday" << endl;
//
//    Date date = today;
//    today.Print();
//    date.Print();
//}
//void Test2()
//{
//    Date today(2023, 11, 16);
//    Date yesterday(2023,11,16);
//
//    Date date1 = today + -10000;
//    Date date2 = yesterday - -10000;
//    date1.Print();
//    date2.Print();
//
//    today -= -10000;
//    today.Print();
//    yesterday += -10000;
//    yesterday.Print();
////     int dif = yesterday - today;
////     cout << dif << endl;
//
//}
//void Test3()
//{
//    Date today(2023, 11, 16);
//    Date yesterday(2023,11,16);
//    Date date = today++;
//    date.Print();
//    today.Print();
//    ++today;
//    today.Print();
//
//    yesterday--;
//    yesterday.Print();
//    --yesterday;
//    yesterday.Print();
//
//}
//int main()
//{
////    Test1(); //> == >= < <= != =
////    Test2(); //+天数 -天数 +=天数 -=天数 -日期
////    Test3(); // ++ --
//
//    return 0;
//}
//#include "test.h"
//void Test()
//{
//    Date today(2003,10,16);
//    Date yesterday(2006,1,2);
////    cout << date1 << date2 << date3;
////    cin >> date1 >> date2 >> date3;
////    cout << date1 << date2 << date3;
//    if(today > yesterday)
//        cout << "today > yesterday" << endl;
//    if(today < yesterday)
//        cout << "today < yesterday" << endl;
//    if(today == yesterday)
//        cout << "today == yesterday" << endl;
//    if(today <= yesterday)
//        cout << "today <= yesterday" << endl;
//    if(today >= yesterday)
//        cout << "today >= yesterday" << endl;
//    if(today != yesterday)
//        cout << "today != yesterday" << endl;
//}
//void Test2()
//{
//    const Date date1(2003,10,16);
//    Date date2(2006,4,16);
////    date2.Print();
////    date1.Print();
//}
//int main()
//{
//    Test();
////    Test2();
//    return 0;
//}
//#include <iostream>
//using namespace std;
//enum X
//{
//    x1,
//    x2,
//    x3,
//    x4 = 10,
//    x5,
//    x6,
//}X;
//int main()
//{
//    enum Y {
//        x1 = 1,
//        x2 = 20,
//        x3 = 3,
//        x4 = 4,
//    }Y;
//    cout << Y << endl;
//    return 0;
////}
//#include <iostream>
//using namespace std;
//
//class A
//{
//public:
//    explicit A(int ca = 1, int cb = 2, int cc = 3, int cd = 4)
//        : a(ca)
//        , b(cb)
//        , d(cd)
//    {}
//    friend ostream& operator<<(ostream& out, const A& a);
//    ~A()
//    {
//        a = 0;
//        b = 0;
//    }
//private:
//    int a;
//    int& b;
//    const int d;
//};
//ostream& operator<<(ostream& out, const A& a)
//{
//    out << a.a << endl << a.b << endl << a.d << endl;
//    return out;
//}
//
//class B
//{
//public:
//    B(int ce, A& ca)
//        : e(ce)
//        , a(ca)
//    {}
//    friend ostream& operator<<(ostream& out, B& b);
//
//private:
//    int e;
//    A a;
//};
//ostream& operator<<(ostream& out, B& b)
//{
//    out << b.e << endl << b.a << endl;
//    return out;
//}
//
//int main()
//{
//    A class_a(5,6,7,8);
////    B class_b(10, class_a);
//    cout << class_a;
////    cout << class_b;
//
//}
//class A
//{
//public:
//    A(int& a)
//        :_a(a)
//    {}
//    friend ostream& operator<<(ostream& out, A& a);
//private:
//    int& _a;
//};
//ostream& operator<<(ostream& out, A& a)
//{
//    out << a._a;
//    return out;
//}
//class B
//{
//public:
//    B(int a, int ref)
//        :_aobj(a)
//        ,_ref(ref)
//        ,_n(10)
//    {}
//    friend ostream& operator<<(ostream& out, B& b);
//private:
//    A _aobj; // 没有默认构造函数
//    int& _ref; // 引用
//    const int _n; // const
//};
//ostream& operator<<(ostream& out, B& b)
//{
//    out << b._aobj << endl << b._ref << endl << b._n << endl;
//    return out;
//}
//int main()
//{
//    int c = 10;
//    A a(c);
//    cout << a;
////    B b(10,30);
////    cout << b;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year = 1, int month = 1, int day = 1, const int &copy = 1)
//        : _year(year)
//        , _month(month)
//        , _day(day)
//        , _copy(copy)
//    {}
//private:
//    int _year;
//    int _month;
//    int _day;
//    int *_a;
//    const int& _copy;
//
//};
//int main()
//{
//    Date date1(2003, 10, 16, 2023);
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class A
//{
//public:
//    A(int a)
//        :_a(a)
//    {}
//private:
//    int _a;
//};
//class B
//{
//public:
//    B(int b, A& a)
//        :_b(b)
//        ,_A(a)
//    {}
//private:
//    int _b;
//    A _A;
//};
//int main()
//{
//    A a(20);
//    B b(2,a);
//    return 0;
//}
/*
 * using namespace std;
class Date
{
public:
    //全缺省构造函数
    Date(int year = 1, int month = 1, int day = 1);
    //拷贝构造函数
    Date(const Date& date);
    //析构函数
    ~Date();
    //赋值运算符重载=
    Date& operator=(const Date& date);

    //运算符重载 >
    bool operator>(const Date& another) const;
    //运算符重载 ==
    bool operator==(const Date& another) const;
    //运算符重载 <
    bool operator<(const Date& another) const;
    //运算符重载 >=
    bool operator>=(const Date& another) const;
    //运算符重载 <=
    bool operator<=(const Date& another) const;
    //运算符重载 !=
    bool operator!=(const Date& another) const;
    //运算符重载


    //取某年某月的天数
    int GetMonthDay(int year, int month);
    //日期+=天数
    //日期+天数
    //日期-=天数
    //日期-天数
    //日期-日期


    //前置++
    //后置++
    //前置--
    //后置--

    //打印

    //友元函数
    friend ostream& operator<<(ostream& out, Date& date);
    friend istream& operator>>(istream& in, Date& date);
private:
    int _month;
    int _day;
    int _year;
};
//运算流重载 <<
ostream& operator<<(ostream& out, Date& date);
//运算流重载 >>
istream& operator>>(istream& in, Date& date);
//
/
 //全缺省构造函数
Date::Date(int year, int month, int day)
    : _year(year)
    , _month(month)
    , _day(day)
{
    if(year < 1 || month < 1 || month > 12 || _day > GetMonthDay(year, month))
    {
        cout << "非法日期" << endl;
        assert(false);
    }
}
//拷贝构造函数
Date::Date(const Date& date)
{
    _year = date._year;
    _month = date._month;
    _day = date._day;
}
//析构函数
Date::~Date()
{
    _year = 0;
    _month = 0;
    _day = 0;
}
//赋值运算符重载
Date& Date::operator=(const Date& date)
{
    if(this != &date)
    {
        _year = date._year;
        _month = date._month;
        _day = date._day;
    }
    return *this;
}


//    //运算符重载 >
bool Date::operator>(const Date& another) const
{
    if(_year > another._year)
        return true;
    else if(_year == another._year && _month > another._month)
        return true;
    else if(_year == another._year && _month == another._month && _day > another._day)
        return true;
    return false;
}
//    //运算符重载 ==
bool Date::operator==(const Date& another) const
{
    return _year == another._year && _month == another._month && _day == another._day;
}
//    //运算符重载 <
bool Date::operator<(const Date& another) const
{
    return !(*this > another || *this == another);
}
//    //运算符重载 >=
bool Date::operator>=(const Date& another) const
{
    return !(*this < another);
}
//    //运算符重载 <=
bool Date::operator<=(const Date& another) const
{
    return !(*this > another);
}
//    //运算符重载 !=
bool Date::operator!=(const Date& another) const
{
    return !(*this == another);
}


//取某年某月的天数
int Date::GetMonthDay(int year, int month)
{
    int monthday[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    if(month == 2 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0))
    {
        return 29;
    }
    return monthday[month];
}
//日期+=天数

//日期+天数

//日期-=天数

//日期-天数

//日期-日期



//前置++

//后置++

//前置--

//后置--


//打印


//运算流输出<<
ostream& operator<<(ostream& out, Date& date)
{
    out << date._year << "年" << date._month << "月" << date._day << "日" << endl;
    return out;
}
//运算流输入>>
istream& operator>>(istream& in, Date& date)
{
    in >> date._year >> date._month >> date._day;
    return in;
}
 */
/*

using namespace std;
class Date
{
public:
    Date(int year, int month, int day);
    int GetMonthDay(int year, int month);
    Date& operator+(int day);
    void Print();
private:
    int _year;
    int _month;
    int _day;
};
void Date::Print()
{
    printf("%04d-%02d-%02d\n", _year, _month, _day);
}
Date& Date::operator+(int day)
{
    _day += day;
    while(_day > GetMonthDay(_year, _month))
    {
        _day -= GetMonthDay( _year, _month);
        ++_month;
        if(_month == 13)
        {
            ++_year;
            _month = 1;
        }
    }
    return *this;
}
Date::Date(int year, int month, int day)
{
    if(year < 1 || month < 1 || month > 12 || day > GetMonthDay(year, month))
    {
        cout << "非法日期" << endl;
        assert(false);
    }

    _year = year;
    _month = month;
    _day = day;
}
int Date::GetMonthDay(int year, int month)
{
    int monthday[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    if(month == 2 && ((year % 4 == 0 && year % 100 != 0)|| year % 400 == 0))
        return 29;
    return monthday[month];
}
int main()
{
    int a, b;
    while (cin >> a >> b)
    {
        Date date(a, 1, 0);
        Date yearmonth = date + b;
        yearmonth.Print();
    }
    return 0;
}*/
//}

//#include <iostream>
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year = 1, int month = 1, int day = 1)
//        : _year(year)
//        , _day(month)
//        , _month(day)
//    {}
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date(2003, 10, 16);
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year = 2, int month = 1, int day = 1)
//            : _year(year)
//            , _month(month)
//            , _day(day)
//    {}
//    void Print()
//    {
//        cout << _year << "年" << _month << "月" << _day << "日" << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date = {2003, 10, 16};
//    date.Print();
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class A
//{
//public:
//    A() { ++_scount; }
//    A(const A& t) { ++_scount; }
//    ~A() { --_scount; }
//    static int GetACount() { return _scount; }
//private:
//    static int _scount;
//};
//
//int A::_scount = 0;
//
//void TestA()
//{
//    cout << A::GetACount() << endl;
//    A a1, a2;
//    A a3(a1);
//    cout << A::GetACount() << endl;
//}
//int main()
//{
//    TestA();
//    return 0;
//}
//#include <iostream>
//using namespace std;
//
//namespace wyd
//{
//    int count = 0;
//}
//
//class Date
//{
//public:
//    Date()
//    {
//        wyd::count++;
//        _count++;
//    }
//    Date(const Date& date)
//    {
//        wyd::count++;
//        _count++;
//    }
//    static int GetCount()
//    {
//        return _count;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//    static int _count;
//};
//int Date::_count = 0;
//
//int main()
//{
//    Date date;
//    Date date2(date);
//    cout << wyd::count << endl;
//    cout << date.GetCount() << endl;
//    return 0;
//}
//
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date()
//    {
//        _count++;
//    }
//    Date(const Date& date)
//    {
//        _count++;
//    }
//    static int GetCount()
//    {
//        return _count;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//    static int _count;
//};
//int Date::_count = 0;
//
//int main()
//{
//    Date date;
//    Date date2(date);
//    cout << Date().GetCount() - 1;
//    return 0;
//}
//#include <iostream>
//#include <istream>
//using namespace std;
//class Date
//{
//public:
//    friend istream& operator<<(istream& in, Date& date);
//private:
//    int _year;
//    int _month;
//    int _day;
//
//};
//istream& operator<<(istream& in, Date& date)
//{
//    in << date._year << date._month << date._day;
//    return in;
//}
//int main()
//{
//    Date date;
//    cin << date;
//
//    return 0;
//}
//#include <iostream>
//#include <istream>
//using namespace std;
//class Date
//{
//public:
//    Date& operator++();
//    bool operator<(const Date& another) const;
//    int operator-(const Date& another);
//    Date& operator+=(int day);
//    int GetMonthDay(int year, int month);
//    friend istream& operator>>(istream& in, Date& date);
//
//private:
//    int _year;
//    int _month;
//    int _day;
//    static int n;
//
//};
//int Date::n = 0;
//istream& operator>>(istream& in, Date& date)
//{
//    in >> date._year >> date._month >> date._day;
//    return in;
//}
//bool Date::operator<(const Date &another) const
//{
//    if(_year < another._year)
//        return true;
//    else if(_year == another._year && _month < another._month)
//        return true;
//    else if(_year == another._year && _month == another._month && _day < another._day)
//        return true;
//    else
//        return false;
//}
//int Date::GetMonthDay(int year, int month)
//{
//    int monthday[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
//    if(month == 2 && ((year % 4 == 0 && year % 100 != 0)|| year % 400 == 0))
//        return 29;
//    return monthday[month];
//}
//Date& Date::operator+=(int day)
//{
//    _day += day;
//    if(_day > GetMonthDay(_year, _month))
//    {
//        _day -= GetMonthDay(_year, _month);
//        ++_month;
//        if(_month == 13)
//        {
//            ++_year;
//            _month = 1;
//        }
//    }
//    return *this;
//}
//Date& Date::operator++()
//{
//    *this += 1;
//    return *this;
//}
//int Date::operator-(const Date &another)
//{
//    Date max(*this);
//    Date min(another);
//    if(max < min)
//    {
//        max = another;
//        min = *this;
//    }
//    while(min < max)
//    {
//        ++min;
//        ++n;
//    }
//    if(n == 1)
//        return 2;
//    else
//        return n;
//}
//int main()
//{
//    Date date1;
//    cin >> date1;
//    Date date2;
//    cin >> date2;
//    int dif = date1 - date2;
//    cout << dif << endl;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year)
//    {
//
//        _year = year;
//    }
//    void Print()
//    {
//        cout << _year << endl;
//    }
//private:
//    int _year;
//};
//static Date date(2003);
//int main()
//{
//    date.Print();
//}
//#include <iostream>
//using namespace std;
//class A
//{
//public:
//    A(int a = 0)
//    {
//        cout << "A()" << endl;
//    }
//private:
//    int _a;
//};
//class B
//{
//public:
//    B(int a)
//    {
//        cout << "B()" << endl;
//    }
//private:
//    int _b;
//    A _A;
//};
//int main()
//{
//    B b(2);
//    return 0;
//#include <iostream>
//using namespace std;
//class A
//{
//public:
//    void Print()
//    {
//        cout << "Print()" << endl;
//    }
//private:
//    double _a;
//
//    class B
//    {
//    private:
//        int _b;
//    };
//};
//
//int main()
//{
//    cout << sizeof(A) << endl;
//    return 0;
//}
/////////////////////////////////////////////////
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    void Init(int year, int month, int day)
//    {
//        _year = year;
//        _month = month;
//        _day = day;
//    }
//    void Print()
//    {
//        cout << _year << "年" << _month << "月" << _day << "日" << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date;
//    date.Init(2023, 11, 20);
//    date.Print();
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year, int month, int day)
//        : _year(year)
//        , _month(month)
//        , _day(day)
//    {}
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date(2023, 11, 20);
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    int a[][3] = {};
//    unsigned char c = '\xaa';
//    printf("%c\n",c);
//    return 0;
//}
//int z = 2
//z    x    y
//3(2) 1    4
//2(1) 2    3
//1(0) 3    2
//0(-1)
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date()
//    {
//        _year = 3;
//        _year = 6;
//    }
//    void Print()
//    {
//        cout << _year << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    Date date;
//    date.Print();
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int day)
//        :_day(day)
//    {}
//private:
//    int& _day;
//};
//int main()
//{
//    Date date(16);
//    return 0;
//}
//class Time
//{
//    friend class Date;  // 声明日期类为时间类的友元类，则在日期类中就直接访问Time类中的私有成员变量
//public:
//    Time(int hour = 0, int minute = 0, int second = 0)
//            : _hour(hour)
//            , _minute(minute)
//            , _second(second)
//            ,
//    {}
//
//private:
//    int _hour;
//    int _minute;
//    int _second;
//
//};
//class Date
//{
//public:
//
//    Date(int year = 1900, int month = 1, int day = 1)
//            : _year(year), _month(month), _day(day)
//    {}
//    void SetTimeOfDate(int hour, int minute, int second)
//    {
//        // 直接访问时间类私有的成员变量
//        _t._hour = hour;
//        _t._minute = minute;
//        _t._second = second;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//    Time _t;
//}
//struct stduent
//{
//    int no;
//    char name[20];
////};
//#include <stdio.h>
//#include <stdlib.h>
//typedef struct List
//{
//    struct List* next;
//    int num;
//    int m;
//}SL;
//void Init(SL* plist)
//{
//    plist->next = plist;
//    plist->num = 0;
//    plist->m = 0;
//}
//void SLPush(SL* plist, int i, int j)
//{
//    SL *newcode = (SL*)malloc(sizeof(SL));
//    if(plist->next == plist)
//    {
//        plist->next = newcode;
//        newcode->next = plist;
//        newcode->m = j;
//        newcode->num = i;
//        return;
//    }
//    SL *cur = plist;
//    while(cur->next != plist)
//    {
//        cur = cur->next;
//    }
//    cur->next = newcode;
//    newcode->next = plist;
//    newcode->m = j;
//    newcode->num = i;
//}
//int IsM(SL *plist, int m)
//{
//    SL* one = plist->next;
//    while(one->next != plist)
//    {
//        SL* cur = plist->next;
//        while(cur->next != plist)
//        {
//            SL* next = cur->next;
//            if(next->m == m)
//            {
//                cur->next = next->next;
//                free(next);
//            }
//            cur = cur->next;
//        }
//        cur = plist->next;
//        int j = 0;
//        while(cur->next != plist)
//        {
//            j++;
//            if(j > m)
//            {
//                j = 1;
//            }
//            cur->m = j;
//        }
//    }
//    return plist->next->num;
//}
//int main()
//{
//    int n = 0;
//    int m = 0;
//    scanf("%d %d",&n, &m);
//    SL list;
//    Init(&list);
//    int j = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        j++;
//        if(j > m)
//        {
//            j = 1;
//        }
//        SLPush(&list, i, j);
//    }
//    int last = IsM(&list, m);
//    printf("%d\n",last);
//    return 0;
//}
//#include <stdio.h>
//#include <stdlib.h>
//typedef struct List
//{
//    struct List* next;
//    int num;
//    int m;
//}SL;
//void Init(SL* plist)
//{
//    plist->next = plist;
//    plist->num = 1;
//    plist->m = 0;
//}
//void SLPush(SL* plist, int i)
//{
//    SL *newcode = (SL*)malloc(sizeof(SL));
//    if(plist->next == plist)
//    {
//        plist->next = newcode;
//        newcode->next = plist;
//        newcode->m = 0;
//        newcode->num = i;
//        return;
//    }
//    SL *cur = plist;
//    while(cur->next != plist)
//    {
//        cur = cur->next;
//    }
//    cur->next = newcode;
//    newcode->next = plist;
//    newcode->m = 0;
//    newcode->num = i;
//}
//
//int IsM(SL *plist, int n, int m)
//{
//    if(plist->next == plist)
//        return 1;
//    if(m == 1)
//        return n;
//    plist->m = 1;
//    SL* cur = plist;
//    SL* next = cur->next;
//    int i = 1;
//    while(cur != next)
//    {
//        if(++i > m)
//        {
//            i = 1;
//        }
//        next->m = i;
//        if(next->m == m)
//        {
//            cur->next = next->next;
//            free(next);
//            next = cur->next;
//        }
//        else
//        {
//            cur = next;
//            next = cur->next;
//        }
//    }
//    return cur->num;
//}
//int main()
//{
//    int n = 0;
//    int m = 0;
//    scanf("%d %d",&n, &m);
//    SL *list = (SL*) malloc(sizeof(SL));
//    Init(list);
//
//    for (int i = 2; i <= n; i++)
//    {
//        SLPush(list, i);
//    }
//    int last = IsM(list, n, m);
//    printf("%d\n",last);
//    return 0;
//}
//#include "code.h"
//int main()
//{
//
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date(int year, int month, int day)
//        : _year(year)
//        , _month(month)
//        , _day(day)
//    {
//        cout << "Date()" << endl;
//    }
//    Date(const Date& date)
//    {
//        cout << "Date(const Date& date)" << endl;
//    }
//    static int GetNum()
//    {
//        return _num;
//    }
//    int _year;
//    int _month;
//    int _day;
//    static int _num;
//};
//int Date::_num = 0;
//int main()
//{
//    return 0;
//}
//#include "test.h"
//using namespace std;
//class Date
//{
//public:
//    Date()
//    {
//        cout << "Date()" << endl;
//    }
//    Date(const Date& date)
//    {
//        cout << "Date(const Date& date)" << endl;
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//Date func()
//{
//    Date date;
//    Date date2 = date;
//    Date date3 = date2;
//    return date;
//}
//int main()
//{
//    char *p = new char[1024 * 1024 * 1024];
//    cout << (void*)p << endl;
//
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Solution
//{
//public:
//    void Convert(string date1)
//    {
//        int i = 0;
//        basic_string<char> ch = date1;
//
//        int a = 3;
//        int b = 2;
//        int c = 2;
//        while(*ch)
//        {
//            ++i;
//            if(i < 5)
//            {
//                _year += *ch * pow(10, a);
//                --a;
//            }
//            else if(i > 5 && i < 8)
//            {
//                _month = *ch * pow(10, b);
//                --b;
//            }
//            else
//            {
//                _day = *ch * pow(10, c);
//                --c;
//            }
//        }
//    }
//    int daysBetweenDates(string date1, string date2)
//    {
//        Convert(date1);
//        Convert(date2);
//
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//int main()
//{
//    return 0;
////}
//int main()
//{
//    char *p = new char[100];
//    delete []p;
//    return 0;
//}
//#include <iostream>
//class A
//{
//public:
//    A(int a = 0)
//        : _a(a)
//    {}
//private:
//    int _a;
//};
//int main()
//{
//    A *a = (A*)malloc(sizeof(A));
//    a -> A(3);
//    return 0;
//}
//#include <iostream>
//template <typename T>
//void Swap(T& a, T& b)
//{
//    T c = a;
//    a = b;
//    b = c;
//}
//int main()
//{
//    int a = 0;
//    int b = 3;
//    Swap(a, b);
//    return 0;
//}
//#include <iostream>
//using namespace std;
//void operator
//int main()
//{
//    return 0;
//}
//#include <iostream>
//using namespace std;
//int main()
//{
//    //开辟一个整型的空间，没有初始化
//    int *a = new int;
//    //开辟一个double类型的空间，并且初始化
//    double *b = new double(3);
//    //开辟连续5个int类型的空间，没有初始化
//    int *arr1 = new int[5];
//    //开辟连续5个int类型的空间，并初始化
//    int *arr2 = new int[5]{1,2,3,4,5};
//    for (int i = 0; i < 5; ++i)
//    {
//        cout << arr2[i] << ' ';
//    }
//    cout << endl;
//    delete a;
//    delete b;
//    delete [] arr1;
//    delete [] arr2;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//int main()
//{
//    //开辟一个整型的空间，没有初始化
//    int *a = new int;
//    //开辟一个double类型的空间，并且初始化
//    double *b = new double(3);
//    //开辟连续5个int类型的空间，没有初始化
//    int *arr1 = new int[5];
//    //开辟连续5个int类型的空间，并初始化
//    int *arr2 = new int[5]{1,2,3,4,5};
//    for (int i = 0; i < 5; ++i)
//    {
//        cout << arr2[i] << ' ';
//    }
//    cout << endl;
//    delete a;
//    delete b;
//    delete [] arr1;
//    delete [] arr2;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Stack
//{
//public:
//    void Init(int capacity)
//    {
//        _a = (int*)malloc(sizeof(int) * capacity);
//        if(_a == nullptr)
//        {
//            perror("malloc fail");
//            exit(-1);
//        }
//        _size = 0;
//        _capacity = capacity;
//    }
//private:
//    int *_a;
//    int _size;
//    int _capacity;
//};
//int main()
//{
//    Stack *st = (Stack*)malloc(sizeof(Stack));
//    int *a = new int;
//    int *b = new int(3);
//    st->Init(4);
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Stack
//{
//public:
//    Stack(int capacity = 4, int size = 0, int num = 0)
//        : _a(new int[capacity]{0})
//        , _size(size)
//        , _capacity(capacity)
//    {
//        cout << "Stack(int capacity = 4)" << endl;
//    }
//
//private:
//    int *_a;
//    int _size;
//    int _capacity;
//};
//int main()
//{
//    Stack *st = new Stack;
//    return 0;
//}#include <iostream>
//using namespace std;
//class Stack
//{
//public:
//    Stack(int capacity = 4, int size = 0, int num = 0)
//        : _a(new int[capacity]{0})
//        , _size(size)
//        , _capacity(capacity)
//    {
//        cout << "Stack(int capacity = 4)" << endl;
//    }
//
//private:
//    int *_a;
//    int _size;
//    int _capacity;
//};
//int main()
//{
//    Stack *st = new Stack;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class A
//{
//public:
//    A()
//    {
//        cout << "A()" << endl;
//    }
////    ~A()
////    {
////        cout << "~A()" << endl;
////    }
//};
//int main()
//{
//    A *a = new A[5];
//    delete a;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Stack
//{
//public:
//    Stack(int capacity = 4, int size = 0, int num = 0)
//            : _a(new int[capacity]{0})
//            , _size(size)
//            , _capacity(capacity)
//    {
//        cout << "Stack(int capacity = 4)" << endl; //方便观察确实调用了构造函数
//    }
//
//private:
//    int *_a;
//    int _size;
//    int _capacity;
//};
//int main()
//{
//    Stack *st = new Stack[5];
//    delete st;
//    return 0;
//}
//#include <iostream>
//using std::cin;
//using std::cout;
//using std::endl;
//char* Compression(char *fast, char *slow)
//{
//    char *newstr = new char[500];
//
//    char *cur = newstr;
//
//    while(*fast)
//    {
//        int count = 0;
//        while(*fast == *slow)
//        {
//            ++count;
//            ++fast;
//        }
//
//        *cur = *slow;
//        ++cur;
//        *cur = count + 48;
//        ++cur;
//        slow = fast;
//    }
//
//    return newstr;
//}
//int main()
//{
//    char str[500] = "\0";
//    cin >> str;
//    char *newstr = Compression(str, str);
//
//    if(strlen(str) <= strlen(newstr))
//    {
//        cout << "NO" << endl;
//        return 0;
//    }
//
//    cout << newstr << endl;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//int main()
//{
//    char str[10] = "\0";
//    fgets(str, 10, stdin);
//    char *cur = str;
//    int count = 0;
//    while(*cur)
//    {
//        if(*cur == ' ' || *cur == '\n');
//        else
//        {
//            ++count;
//        }
//        ++cur;
//    }
//    cout << count << endl;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//
//template<class T, class Y>
//T Add(const T& a,const Y& b)
//{
//    return a + b;
//}
//int main()
//{
//    cout << Add(1,2.2) << endl;
//    cout << Add('s', 3.2) << endl;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//template<class T>
//class Sqt
//{
//public:
//    Sqt(int capacity = 4)
//        : _a(new T[capacity])
//        , _size(0)
//        , _capacity(capacity)
//    {}
//    ~Sqt()
//    {
//        if(_a != nullptr)
//        {
//            delete []_a;
//        }
//        _a = nullptr;
//        _size = _capacity = 0;
//    }
//private:
//    T *_a;
//    int _size;
//    int _capacity;
//};
//int main()
//{
//    Sqt<int> sqi;
//    Sqt<double> sqd;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class A
//{
//public:
//    A()
//    {
//        cout << "A()" << endl;
//    }
//    A(const A& a)
//    {
//        cout << "A(const A& a)" << endl;
//    }
//    A& operator=(const A& another)
//    {
//        cout << "A& operator=(const A& another)" << endl;
//        return *this;
//    }
//    ~A()
//    {
//        cout << "~A()" << endl;
//    }
//private:
//    int _a;
//};
//int main()
//{
//    A a1;
//    A a3;
//    A a2 = a1;
//    a3 = a1;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//void Swap(int& a, int& b)
//{
//    int tmp = a;
//    a = b;
//    b = tmp;
//}
//void Swap(double& a, double& b)
//{
//    double tmp = a;
//    a = b;
//    b = tmp;
//}
//void Swap(char& a, char& b)
//{
//    char tmp = a;
//    a = b;
//    b = tmp;
//}
//
//int main()
//{
//    return 0;
//}
//#include <iostream>
//using namespace std;
//template<class T>
//T GetNum(int n)
//{
//    T b = n;
//    return b;
//}
//int main()
//{
//    int a = 3;
//    int b = 4;
//    int c = GetNum<int>(a);
//    return 0;
//}
//#include <iostream>
//using namespace std;
//template<class T, class Y>
//Y Add(const T& a, const Y& b)
//{
//    return a + b;
//}
//int main()
//{
//    int a = 3;
//    double b = 4.7;
//    cout << Add(a, b) << endl;
//    return 0;
//#include <iostream>
//using namespace std;
//
//template <class T>
//class Stack
//{
//public:
//    Stack(int capacity = 4)
//            : _a(new T[capacity])
//            , _size(0)
//            , _capacity(capacity)
//    {}
//    ~Stack();
//private:
//    T *_a;
//    int _size;
//    int _capacity;
//};
//
//template<class T>
//Stack<T>::~Stack()
//{
//    delete []_a;
//    _a = nullptr;
//    _size = _capacity = 0;
//}
//
//int main()
//{
//    Stack<int> st;
//    return 0;
//}
//#include <iostream>
////void Print()
////{
////    void Swap()
////    {
////        ;
////    }
////}
//int main() {
//    char c1,c2;
//    int a1,a2;
//    c1 = getchar();
//    scanf("%2d",&a1);
//    c2 = getchar();
//    scanf("%3d",&a2);
//    printf ("%d,%d,%c,%c\n",a1,a2,c1,c2);
//}
//#include <iostream>
////void Print()
////{
////    void Swap()
////    {
////        ;
////    }
////}
//using namespace std;
//int main()
//{
//    int a = 3;
//
//    int *pa = &a;
//    int& b = a;
//
//
//    return 0;
//}
//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
//    string s1;
//    string s2("hello world");
////    string s3 = "hello world";
////    string s4(s2);
////    string s5(4, 'x');
////    string s6({'y', 'x', 'y'});
////    cout << s1 << endl;
////    cout << s2 << endl;
////    cout << s3 << endl;
////    cout << s4 << endl;
////    cout << s5 << endl;
////    cout << s6 << endl;
////    cout << size(s1) << endl;
////    cout << size(s2) << endl;
////    cout << size(s3) << endl;
////    cout << size(s4) << endl;
////    cout << size(s5) << endl;
////    cout << size(s6) << endl;
////    cout << s2.capacity() << endl;
////    cout << s2.size() << endl;
////    cout << s1.empty() << endl;
////    cout << s2.empty() << endl;
//    return 0;
//}
//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
////    string s1;
//    string s2("hello");
//    cout << s2.size() << endl;
//    s2.resize(3);
//    cout << s2.size() << endl;
//    cout << s2 << endl;
////    s2.reserve(100);
////    string s3 = "hello world";
////    string s4(s2);
////    string s5(4, 'x');
////    string s6({'y', 'x', 'y'});
////    s2.clear();
////    cout << s1 << endl;
////    cout << s2 << endl;
////    if(s1.empty())
////        cout << "s1" << endl;
////    if(s2.empty())
////        cout << "s2" << endl;
////    cout << s1.empty() << endl;
//    cout << s2.capacity() << endl;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class String
//{
//public:
//    String()
//
//    {}
//private:
//    char *_str;
//};
//int main()
//{
//
//    return 0;
//}
/**
 * class Solution
{
public:
    int firstUniqChar(string s)
    {
        int size = s.size();
        int i = 0;
        while(size--)
        {
            string::iterator str = s.begin() + i;
            string::iterator begin = s.begin();
            string::iterator end = s.end();
            int flag = 0;
            while(begin < end)
            {
                if(str != begin && *str == *begin)
                {
                    flag = 1;
                    break;
                }
                ++begin;
            }
            if(flag == 0)
                return i;
            ++i;
        }
        return -1;
    }
};
 #include <cmath>
#include <iterator>
class Solution
{
public:
    int StrToInt(string str)
    {
        string::iterator it = str.begin();
        if(*it == '+' || *it == '-' || (*it >=48 && *it <= 57))
        {
            ++it;
            while(it != str.end())
            {
                if(*it < 48 || *it > 57)
                    return 0;
                it++;
            }
        }
        else
            return 0;

        int sum = 0;
        int i = 0;
        it = str.end() - 1;
        while(it != str.begin())
        {
            sum = sum + (*it-48) * pow(10, i);
            ++i;
            --it;
        }
        if(*it == '-')
            return -1*sum;
        else if(*it == '+')
            return sum;
        else
        {
            sum = sum + (*it-48) * pow(10, i);
            return sum;
        }
    }
    class Solution
{
public:
    void Swap(char& str1, char& str2)
    {
        char tmp = str1;
        str1 = str2;
        str2 = tmp;
    }
    void reverseString(vector<char>& s)
    {
        vector<char>::iterator begin = s.begin();
        vector<char>::iterator end  =s.end() - 1;
        while(begin < end)
        {
            Swap(*begin, *end);
            ++begin;
            --end;
        }
    }
 */
//#include <iostream>
//using namespace std;
//template<class T, int A>
//int Swap()
//{
//    return A;
//}
//int main()
//{
//    cout << Swap<int ,10>() << endl;
//    return 0;
//}
///**
// * class Solution {
//public:
//    string reverseOnlyLetters(string s)
//    {
//        string::iterator begin = s.begin();
//        string::iterator end = s.end() - 1;
//        while(begin < end)
//        {
//            while(begin < end && (*begin < 'A' || (*begin > 'Z' && *begin < 'a') || *begin > 'z'))
//                ++begin;
//            while(begin < end && (*end <'A' || (*end > 'Z' && *end < 'a') || *end > 'z'))
//                --end;
//            swap(*begin, *end);
//            ++begin;
//            --end;
//        }
//        return s;
//    }
//};
//#include <iostream>
//#include <string>
//using namespace std;
//class Count
//{
//public:
//
//private:
//
//};
//    int firstUniqChar(string s)
//    {
//        int arr[256] = {0};
//        string::iterator begin = s.begin();
//        while(begin < s.end())
//        {
//            ++arr[*begin];
//            ++begin;
//        }
//        begin = s.begin();
//        for(int i = 0; begin + i < s.end(); i++)
//        {
//            if(arr[*(begin + i)] == 1)
//                return i;
//        }
//        return -1;
//    }
//int main()
//{
//    string s = "leetcode";
//    cout << firstUniqChar(s) << endl;
//    return 0;
//}
//#include <stdio.h>
//#include <stdlib.h>
//
//int main()
//{
//   int arr[] = {0,1,3,6,10,15,21,28,36,45};
//    int sum = 0;
//    for(int i = 100; i < 1000; i++)
//    {
//        int x = i;
//        while(x)
//        {
//            sum += arr[x%10];
//            x /= 10;
//        }
//        if(i == sum)
//            printf("%d\n", i);
//    }
//    return 0;
//}
//
//#include <stdio.h>
//#include <stdlib.h>
//
//int main()
//{
//    int arr[] = {0,1,3,6,10,15,21,28,36,45};
//    int sum = 0;
//    for(int i = 100; i < 1000; i++)
//    {
//        int x = i;
//        while(x)
//        {
//            sum += arr[x%10];
//            x /= 10;
//        }
//        if(i == sum)
//            printf("%d\n", i);
//    }
//    return 0;
//}
//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
//    string str;
//    str.reserve(20);
//    cout << str.capacity() << endl;
//    str.reserve(10);
//    cout << str.capacity() << endl;
//
//    return 0;
////}
//#include <iostream>
//using namespace std;
//int main()
//{
//    int arr[10] = {0};
//    scanf("%d",&arr);
//    for(auto e : arr)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//    return 0;
//}
//}
//#include <iostream>
//#include <string>
//using namespace std;
//string addStrings(string num1, string num2)
//{
//    string big = num1;
//    string small = num2;
//    string::iterator bigend = big.end() - 1;
//    string::iterator smallend = small.end() - 1;
//    if(big.size() < small.size())
//    {
//        big = num2;
//        small = num1;
//        bigend = big.end() - 1;
//        smallend = small.end() - 1;
//    }
//
//    while(smallend >= small.begin())
//    {
//        int smallnum = *smallend - '0';
//        int bignum = *bigend - '0';
//        int sum = smallnum + bignum;
//        if(sum >= 10)
//        {
//            if(bigend == big.begin())
//            {
//                sum %= 10;
//                *bigend = sum + '0';
//                big.insert(big.begin(),'1');
//            }
//            else
//            {
//                ++(*(bigend-1));
//                sum %= 10;
//                *bigend = sum + '0';
//            }
//
//        }
//        else
//        {
//            *bigend = sum + '0';
//        }
//        --smallend;
//        --bigend;
//    }
//    while(bigend >= big.begin())
//    {
//        int bignum = *bigend - '0';
//        if(bigend == big.begin())
//        {
//            if(bignum >= 10)
//            {
//                bignum %= 10;
//                *bigend = bignum + '0';
//                big.insert(big.begin(),'1');
//            }
//            else;
//        }
//        else
//        {
//            if(bignum >= 10)
//            {
//                ++(*(bigend-1));
//                bignum %= 10;
//                *bigend = bignum + '0';
//            }
//            else;
//        }
//        --bigend;
//    }
//    return big;
//}
//int main()
//{
//    string s1 = "1";
//    string s2 = "9";
//    string s3 = addStrings(s1, s2);
//    cout << s3 << endl;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//#include <stdio.h>
//union a
//{
//
//};
//int main()
//{
//    printf("%d\n", sizeof(void));
//    return 0;
//}
//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
//    string s1;
//    string s2("hello world");
//    string s4 = s2;
//    string s3(s2);
//    cout << s4 << endl;
//    cout << s3 << endl;
//    string s5 = "hello world";
//    cout << s5 << endl;

//    string s5 = 'x';
//    string s6;
//    s6 = 'x';
//    cout << s6 << endl;
//    string s7 = "hello world";
//    string s8(s7, 0, 3);
//    cout << s8 << endl;
//    string s9("hello world", 4);
//    cout << s9;
//    string s10(10, 'x');
//    cout << s10;
//    string s11 = "hello world";
//    string s12(s11.begin(), s11.end()-1);
//    cout << s12;
//    int len = s1.size();
//    cout << len << endl;
//    cout << s1.capacity() << endl;
//    string s1 = "hello world";
//    cout << s1.empty() << endl;
//    string s2;
//    cout << s2.empty() << endl;
//    string s3 = "hello world";
//    cout << "清空之前的容量：" << s3.capacity() << endl;
//    cout << "清空之前的长度：" <<s3.size() << endl;
//
//    s3.clear();
//    cout << "清空之后的容量：" << s3.capacity() << endl;
//    cout << "清空之后的长度：" <<s3.size() << endl;
//    string s4 = "hello world";
//    cout << "缩容之前的容量：" << s4.capacity() << endl;
//    s4.reserve(2);
//    cout << "缩容之后的容量：" << s4.capacity() << endl;

//    string s5 = "hello world";
//    cout << s5 << endl;
//    cout << "调整有效字符之前的容量：" << s5.capacity() << endl;
//    cout << "调整有效字符之前的长度：" <<s5.size() << endl;
//
//    s5.resize(30, 'x');
//    cout << s5 << endl;
//    cout << "调整有效字符之后的容量：" << s5.capacity() << endl;
//    cout << "调整有效字符之后的长度：" <<s5.size() << endl;
//    cout << s1[0] << endl;
//    string::reverse_iterator  rb = s1.rbegin();
//    string::reverse_iterator re = s1.rend();
//    while(re >= rb)
//    {
//        cout << *re << ' ';
//        --re;
//    }
//    for(auto e : s1)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//    string s1 = "hello world";
//    cout << s1 << endl;
//    s1 += " hello CSDN";
//    cout << s1 << endl;
//    string s1;
//    getline(cin, s1);
//    cout << s1 << endl;
//    return 0;
//
//}
//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
//    string s1("Test.cpp.cpppp");
//    int pos = s1.rfind('.');
//    if(pos != string::npos)
//    {
//        cout << s1.substr(pos, s1.size() - pos) << endl;
//    }
//    return 0;
//}
//#include <iostream>
//using namespace std;
//namespace wyd
//{
//    class string
//    {
//    public:
//        string(const char *str)
//            : _num(strlen(str))
//            , _str(new char[_num + 1])
//            , _size(_num)
//            , _capacity(_num)
//        {
//            strcpy(_str, str);
//        }
//    private:
//        size_t _num;
//        char *_str;
//        size_t _size;
//        size_t _capacity;
//    };
//}
//int main()
//{
//    wyd::string s("hello world");
//    return 0;
//}
//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
////    string s2 = "CSDN";
////
////    cout << "插入之前：" << s1 << endl;
////    s1.insert(1, s2);
////    cout << "插入之后：" << s1 << endl;
////    string s1 = "hello world";
////    cout << "删除之前：" << s1 << endl;
////    s1.erase(s1.begin(), s1.end()-1);
////    cout << "删除之后：" << s1 << endl;
//    string s2 = "hello world";
//    size_t n = s2.find('w', 0);
//    string s3 = s2.substr(n,s2.size() - n);
//    if(s2 < s3)
//        cout << s2;
//    else
//        cout << s3;
//    return 0;
////}
//#include <iostream>
//using namespace std;
//int main()
//{
////    float a = 1.1;
////    double b = 2.2;
////    printf("%f\n", a);
////    printf("%lf\n", b);
////    printf("%lf\n", a+b);
//
//    size_t c = 1;
//    unsigned d = 1;
//    printf("%zu\n", c);
//    printf("%u\n", d);
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    int b;
//    printf("helloworld %n12345\n", &b);
//    printf("%d\n", b);
//    return 0;
//}
//#include <iostream>
//using namespace std;
//int main()
//{
//
//    string a="hello world";
//    string b=a;
//
//    if (a.c_str()==b.c_str())
//        cout<<"true"<<endl;    //true
//    else
//        cout<<"false"<<endl;
//
//    string c=b;
//    c="";
//
//    if (a.c_str()==b.c_str())     //
//        cout<<"true"<<endl;
//    else
//        cout<<"false"<<endl;
//
//    a="";
//
//    if (a.c_str()==b.c_str())
//        cout<<"true"<<endl;
//    else
//        cout<<"false"<<endl;
//
//    return 0;
//}
//int main(int argc, char *argv[])
//{
//    string strText = "How are you?";
//    string strSeparator = " ";
//    string strResult;
//
//    int size_pos = 0;
//    int size_prev_pos = 0;
//    while((size_pos = strText.find_first_of(strSeparator, size_pos)) != string::npos)
//    {
//        strResult = strText.substr(size_prev_pos, size_pos-size_prev_pos);
//        cout<<strResult<<" ";
//        size_prev_pos = ++size_pos;
//    }
//
//    if(size_prev_pos != strText.size())
//    {
//        strResult = strText.substr(size_prev_pos, size_pos-size_prev_pos);
//        cout<<strResult<<" ";
//    }
//
//    cout<<endl;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//class Solution
//{
//public:
//    string reverseStr(string s, int k)
//    {
//        if(s.size() < k)
//        {
//            reverse(s.begin(), s.end()-1);
//            return s;
//        }
//
//        int count  = 0;
//        string::iterator cur = s.begin();
//        while(cur < s.end())
//        {
//            ++count;
//            int remaining = s.size - count;
//            if(remaining < k)
//            {
//                reverse(s.begin() + count, s.end());
//                return s;
//            }
//            else if(remaining >= k && remaining < 2k)
//            {
//                reverse(s.begin(), s.begin() + k);
//            }
//            else;
//            ++cur;
//        }
//
//        return s;
//    }
//};
//string reverseStr(string s, int k)
//{
//    // if(s.size() < k)
//    // {
//    //     reverse(s.begin(), s.end()-1);
//    //     return s;
//    // }
//
//    int count  = 0;
//    string::iterator cur = s.begin();
//    while(cur < s.end())
//    {
//        ++count;
//        int remaining = s.size() - count;
//        if(remaining < k)
//        {
//            reverse(s.begin() + count, s.end());
//            return s;
//        }
//        else if(remaining >= k && remaining < 2 * k)
//        {
//            reverse(s.begin() + count, s.begin() + count + k);
//        }
//        else;
//        if(count % (2 * k) == 0)
//        {
//            int num = 0;
//            if(count != 2*k)
//                num = count;
//            reverse(s.begin() + num, s.begin() + num + k);
//        }
//        else;
//
//        ++cur;
//    }
//
//    return s;
////}
//string reverseStr(string s, int k)
//{
//    // if(s.size() < k)
//    // {
//    //     reverse(s.begin(), s.end()-1);
//    //     return s;
//    // }
//
//    int count  = 0;
//    while(count < s.size())
//    {
//        int rem = s.size() - count;
//        if(rem < k)
//        {
//            reverse(s.begin()+s.size()-count, s.end());
//        }
//        else if(rem >= k && rem < 2*k)
//        {
//            reverse(s.begin()+s.size()-count, s.begin()+s.size()-count+k);
//        }
//        if(count != 0 && count % 2 * k == 0)
//        {
//            int num = count - 2*k;
//            reverse(s.begin()+num, s.begin()+num+k);
//        }
//        count += 2*k;
//
//    }
//
//    return s;
//}
//#pragma pack(2)
//class A
//{
//    int i;
//    union U
//    {
//        char str[13];
//        int i;
//    }u;
//    void func() {};
//    typedef char* cp;
//    enum
//    {
//        red,
//        green,
//        blue
//    }color;
//};
//enum
//{
//    a,
//    b
//}A;
//int main()
//{
////    scanf("");
////    cout << sizeof(A) << endl;
//    int arr[3] = {1,2,3};
//    cout << *(arr) << endl;
//    return 0;
//}
//struct A
//{
//    int a:16;
//}a;
//int main()
//{
//
//    cout << sizeof(A) << endl;
//    cout << a.a << endl;
//}
//#include <stdio.h>
//struct T
//{
//    char a;
//    int *d;
//    int b;
//    int c:16;
//    double e;
//};
//struct S
//{
//    char a:3;
//    char b:4;
//    char c:5;
//    char d:4;
//};
//int main()
//{
//    struct S s = {0};
//    s.a = 10;
//    s.b = 12;
//    s.c = 3;
//    s.d = 4;
////    printf("%lu\n", sizeof(s));
//    printf("%d %d %d %d\n",s.a, s.b, s.c, s.d);
//    1/010
//    /1100
//    /00011
//    /0100
//    return 0;
//}

//int main()
//{
//    string num1 = "123";
//    string num2 = "456";
//    cout << multiply(num1, num2) << endl;
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    float a = 0;
//    int b = 0;
//    char c = '1';
//    scanf(" %c", &c);
//    printf("c=%c\n", c);
//}
//#include <iostream>
//#include <string>
//using namespace std;
//string addStrings(string num1, string num2)
//{
//    string big = num1;
//    string small = num2;
//    string::iterator bigend = big.end() - 1;
//    string::iterator smallend = small.end() - 1;
//    if(big.size() < small.size())
//    {
//        big = num2;
//        small = num1;
//        bigend = big.end() - 1;
//        smallend = small.end() - 1;
//    }
//
//    int next = 0;
//    while(smallend >= small.begin() || bigend >= big.begin())
//    {
//        int smallnum = 0;
//        int bignum = 0;
//
//        if(smallend >= small.begin())
//            smallnum = *(smallend--) - '0';
//        if(bigend >= big.begin())
//            bignum = *(bigend--) - '0';
//
//        int sum = smallnum + bignum + next;
//        next = sum / 10;
//        sum %= 10;
//        *(bigend+1) = sum + '0';
//
//    }
//    if(next == 1)
//    {
//        big.insert(big.begin(), '1');
//    }
//    return big;
//}
//string multiply(string num1, string num2)
//{
//    string big = num1;
//    string small = num2;
//    if(num1.size() < num2.size())
//    {
//        big = num2;
//        small = num1;
//    }
//    string::iterator bend = big.end() - 1;
//    string add1;
//    string add2 = "0";
//    int bcount = 0;
//    while(bend >= big.begin())
//    {
//        string::iterator send = small.end() - 1;
//        int scount = 0;
//        while(send >= small.begin())
//        {
//            int num = (*bend-'0')*(*send-'0');
//            if(num == 0)
//            {
//                add1 += '0';
//            }
//            while(num > 0)
//            {
//                add1 += num % 10 + '0';
//                num /= 10;
//            }
//            reverse(add1.begin(), add1.end());
//            string zeronum(scount+bcount, '0');
//            add1 += zeronum;
//            add2 = addStrings(add1, add2);
//            add1 = "\0";
//            --send;
//            ++scount;
//        }
//        --bend;
//        ++bcount;
//    }
//    return add2;
//}
//int main()
//{
//    string num1 = "9";
//    string num2 = "9";
//    cout << multiply(num1, num2) << endl;
//    return 0;
//}
/**
 * class Solution
{
public:
    bool isPalindrome(string s)
    {
        string copy;
        for(auto e : s)
        {
            if((e >= '0' && e <= '9') || (e >= 'a' && e <= 'z'))
            {
                copy += e;
            }
            else if(e >= 'A' && e <= 'Z')
            {
                copy += e + 'a' - 'A';
            }
            else;
        }
        string::iterator begin = copy.begin();
        string::iterator end = copy.end() - 1;
        while(begin < end)
        {
            if(*begin != *end)
            {
                return false;
            }
            ++begin;
            --end;
        }
        return true;
    }
    class Solution
{
public:
    string reverseWords(string s)
    {
        string::iterator cur = s.begin();
        string::iterator next = s.begin();
        while(next <= s.end())
        {
            if(*next == ' ' || next == s.end())
            {
                string::iterator right = next - 1;
                string::iterator left = cur;
                while(left < right)
                {
                    swap(*left, *right);
                    ++left;
                    --right;
                }
                cur = next + 1;
            }
            ++next;
        }
        return s;
    }

};

 */

//#include "test.h"
//void Test1()
//{
//    bit::string s1("hello world");
//    bit::string s2("hello Linux!123456");
//    s1.swap(s2);
//    s1 += "12345678910111213141516";
//    s2.resize(5,'w');
//    bit::string s3;
//    s1 = s2;
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1 += 'l';
//    s1[0] = 48;
//    cout << s1 << endl;
//    cout << s2  << endl;

//}
//void Test2()
//{
//    bit::string s1("hello ");
////    bit::string s2("world");
//    s1 += "world";
////    s1 += 'c';
//    cout << s1.size() << endl;
//    cout << s1.capacity() << endl;
//    s1.clear();
//    cout << s1.size() << endl;
//    cout << s1.capacity() << endl;
//    cout << s1;
//
//}
//void Test3()
//{
//    bit::string s1 = "helloworld";
//    bit::string::iterator begin = s1.begin();
//    while(begin < s1.end())
//    {
//        cout << *(begin++) << ' ';
//    }
//    cout << endl;
//    for(auto e: s1)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//}
//void Test4()
//{
//    bit::string s1 = "hello";
//    bit::string s2 = "lalalala";
//    cout << s1 << endl << s2 << endl;
//    s1.swap(s2);
//    cout << s1 << endl << s2 << endl;
//}
//void Test5()
//{
//    string str("https://legacy.cplusplus.com/reference/string/string/substr/");
//	string sub1, sub2, sub3;
//	size_t pos1 = str.find(':');
//	sub1 = str.substr(0, pos1 - 0);
//	cout << sub1 << endl;
//
//	size_t pos2 = str.find('/', pos1+3);
//	sub2 = str.substr(pos1 + 3, pos2 - (pos1 + 3));
//	cout << sub2 << endl;
//
//	sub3 = str.substr(pos2 + 1);
//	cout << sub3 << endl;
//    bit::string s1 = "hellololoo";
//    bit::string s2 = "ll";
////    swap(s1, s2);
//    bit::string half = s1.substr(1);
//    cout << half << endl;
////    cout << s1.find("lo", 4) << endl;
////    s1.erase(1);
////    cout << s1 << endl;
//}
//void Test6()
//{
//
//}
//int main()
//{
////    Test1();//测试构造
////    Test2(); //测试尾插
////    Test3();//测试迭代器
////    Test4(); //测试交换函数
//    Test5();
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    int arr[] = {1,2,3,4,5};
//    short *p = (short*)arr;
//    int i = 0;
//    for(i=0; i<4; i++)
//    {
//        *(p+i) = 0;
//    }
//
//    for(i=0; i<5; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//    return 0;
//}
//#include "test.h"
//size_t bit::string::npos = -1;
//bit::string::string(const char *str)
//{
//    _size = _capacity = strlen(str);
//    _str = new char[_capacity + 1];
//    strcpy(_str, str);
//}
//bit::string::string(const bit::string& s)
//{
//    _size = s._size;
//    _capacity = s._capacity;
//    _str = new char[_capacity + 1];
//    strcpy(_str, s._str);
//}
//bit::string::~string()
//{
//    if(_str != nullptr)
//    {
//        delete []_str;
//        _str = nullptr;
//        _size = _capacity = 0;
//    }
//}
//bit::string& bit::string::operator=(const bit::string& s)
//{
//    if(this != &s)
//    {
//        char *tmp = new char[s._capacity + 1];
//        strcpy(tmp, s._str);
//        delete []_str;
//
//        _str = tmp;
//        _size = s._size;
//        _capacity = s._capacity;
//    }
//    return *this;
//}
//
//bit::string::iterator bit::string::begin()
//{
//    return _str;
//}
//
//bit::string::iterator bit::string::end()
//{
//    return _str + _size;
//}
//
//size_t bit::string::size() const
//{
//    return _size;
//}
//
//size_t bit::string::capacity() const
//{
//    return _capacity;
//}
//
//bool bit::string::empty() const
//{
//    return _size == 0;
//}
//
//void bit::string::reserve(size_t n)  //只扩容不缩容
//{
//    if(n > _capacity)
//    {
//        _capacity = n;
//        char *newstr = new char[_capacity + 1];
//        strcpy(newstr, _str);
//        delete []_str;
//        _str = newstr;
//    }
//}
//
//void bit::string::resize(size_t n, char c)
//{
//    if(n > _size)
//    {
//        if(n > _capacity)
//            reserve(n);
//        for (size_t i = _size; i < n; ++i)
//        {
//            _str[i] = c;
//        }
//        _str[n] = '\0';
//    }
//    _size = n;
//}
//
//ostream& bit::operator<<(std::ostream &out, const bit::string &s)
//{
//    for(int i = 0; i < s.size(); ++i)
//    {
//        out << s._str[i];
//    }
//    return out;
//}
//
//void bit::string::clear()
//{
//    _size = 0;
//}
//
//void bit::string::push_back(char c)
//{
//    if(_size == _capacity)
//        resize(_size+1, c);
//    else
//        _str[_size++] = c;
//}
//
//bit::string& bit::string::operator+=(char c)
//{
//    push_back(c);
//    return *this;
//}
//
//const char *bit::string::c_str() const
//{
//    return _str;
//}
//
//void bit::string::append(const char *str)
//{
//    reserve(_capacity+ strlen(str));
//    strcpy(_str+_size, str);
//    _size += strlen(str);
//}
//
//bit::string &bit::string::operator+=(const char *str)
//{
//    append(str);
//    return *this;
//}
//
//void bit::string::swap(bit::string& s)
//{
//    std::swap(_str, s._str);
//    std::swap(_size, s._size);
//    std::swap(_capacity, s._capacity);
//}
//
//char& bit::string::operator[](size_t index)
//{
//    assert(index < _size);
//    return _str[index];
//}
//
//const char& bit::string::operator[](size_t index) const
//{
//    assert(index < _size);
//    return _str[index];
//}
//
//bool bit::string::operator<(const bit::string &s)
//{
//    return strcmp(_str, s._str) < 0;
//}
//
//bool bit::string::operator==(const bit::string &s)
//{
//    return strcmp(_str, s._str) == 0;
//}
//
//bool bit::string::operator<=(const bit::string &s)
//{
//    return *this == s || *this < s;
//}
//
//bool bit::string::operator>=(const bit::string &s)
//{
//    return !(*this < s);
//}
//
//bool bit::string::operator>(const bit::string &s)
//{
//    return !(*this <= s);
//}
//
//bool bit::string::operator!=(const bit::string &s)
//{
//    return !(*this == s);
//}
//
//size_t bit::string::find(char c, size_t pos) const
//{
//    assert(pos < _size);
//    for (size_t i = pos; i < _size; ++i)
//    {
//        if(_str[i] == c)
//            return i;
//    }
//    return bit::string::npos;
//}
//
//size_t bit::string::find(const char *s, size_t pos) const
//{
//    size_t i = find(*s, pos);
//    if (i == bit::string::npos)
//        return i;
//    while(i < _size)
//    {
//        size_t k = i + 1;
//        int ret = 0;
//        for (int j = 1; j < strlen(s); ++j)
//        {
//            if(_str[k] != s[j])
//            {
//                ret = 1;
//                break;
//            }
//            ++k;
//            if(k > _size)
//                return -1;
//        }
//        if(ret == 0)
//            return i;
//        else
//            i = find(*s, k);
//    }
//    return bit::string::npos;
//}
//
//bit::string& bit::string::erase(size_t pos, size_t len)
//{
//    assert(pos < _size);
//    if(len == npos || pos + len >= _size)
//    {
//        _size = pos;
//        _str[_size] = '\0';
//        return *this;
//    }
//    while(pos + len < _size)
//    {
//        _str[pos] = _str[pos + len];
//        ++pos;
//    }
//    _size -= len;
//    _str[_size] = '\0';
//    return *this;
//}
//
//bit::string bit::string::substr(size_t pos, size_t len) const
//{
//    assert(pos < _size);
//    if(len == npos || pos + len >= _size)
//    {
//        len = _size - pos;
//    }
//    string sstr;
//    sstr.reserve(len);
//    sstr._size = len;
//    strncpy(sstr._str, _str+pos, len);
//    return sstr;
//}
//#include <iostream>
//#include <cstring>
//#include <cassert>
//using namespace std;
//namespace bit
//{
//    class string
//    {
//    public:
//        typedef char *iterator;
//    public:
//
//        string(const char *str = "");
//        string(const bit::string& s);
//        string& operator=(const bit::string& s);
//        ~string();
//
//        iterator begin();
//        iterator end();
//
//        void push_back(char c);
//        string &operator+=(char c);
//        void append(const char *str);
//        string& operator+=(const char *str);
//        void clear();
//        void swap(string &s);
//        const char *c_str() const;
//
//        size_t size() const;
//        size_t capacity() const;
//        bool empty() const;
//        void resize(size_t n, char c = '\0');
//        void reserve(size_t n);
//
//        char& operator[](size_t index);
//        const char& operator[](size_t index) const;
//
//        bool operator<(const string &s);
//        bool operator<=(const string &s);
//        bool operator>(const string &s);
//        bool operator>=(const string &s);
//        bool operator==(const string &s);
//        bool operator!=(const string &s);
//
//////         返回c在string中第一次出现的位置
//        size_t find(char c, size_t pos = 0) const;
//
//////         返回子串s在string中第一次出现的位置
//        size_t find(const char *s, size_t pos = 0) const;
//
//////         在pos位置上插入字符c/字符串str，并返回该字符的位置
////        string &insert(size_t pos, char c);
////        string &insert(size_t pos, const char *str);
//
//////         向后删除pos位置的len个字符
//        string& erase(size_t pos, size_t len = npos);
//        string substr (size_t pos = 0, size_t len = npos) const;
//    private:
//        char *_str;
//        size_t _capacity;
//        size_t _size;
//        static size_t npos;
//        friend ostream& operator<<(ostream& out, const bit::string& s);
//    };
//}
//#include <stdio.h>
//int main()
//{
//    int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
//    printf("%d\n", **(arr + 1));
//    return 0;
//}
//#include<stdio.h>
//int Checkss(int m)
//{
//    for(int i = 2;i < m;i++)
//    {
//        if(m % i == 0)
//            return 0;
//    }
//    return m;
//}
//int main()
//{
//    int sum = 0;
//    for(int i = 2;i <= 51;++i)
//    {
//        sum += Checkss(i);
//    }
//    printf("The result is:%d\n",sum);
//}
//#include <stdio.h>
//int main()
//{
//    int c = 699050;
//    printf("%d\n", (short)c);
//    printf("%d\n", c);
//    return 0;
//}
//#include "test.h"
//int main()
//{
//    bit::string s1;
//    bit::string s2;
//    cin >> s1 >> s2;
//    cout << s1 << endl << s2;
//    return 0;
//////}
//#include <stdio.h>
//int main()
//{
//    char a[10] = "\0"; //初始化一下，防止是随机值
//    char b; //删除的字母
//    for(int i = 0; i < 10; i++)
//    {
//        scanf("%c", &a[i]);
//    }
//
//    getchar(); //清理缓冲区
//
//    printf("请输入你要删除的字母: ");
//    scanf("%c", &b);
//    for(int i = 0; i < 10; i++)
//    {
//        if(a[i] != b) //不是删除的字母
//        {
//            printf("%c", a[i]);
//        }
//    }
//    return 0;
//}
//#include <iostream>
//#include <string>
//using namespace std;
//string addBinary(string a, string b)
//{
//    string big = a;
//    string small = b;
//    if(a.size() < b.size())
//    {
//        big = b;
//        small = a;
//    }
//    string result = "0";
//    result += big;
//
//    string::iterator rend = result.end() - 1;
//    string::iterator send = small.end() - 1;
//    while(send >= small.begin())
//    {
//        *rend += *send - '0';
//        if(*rend >= 2 + '0')
//        {
//            ++(*(rend - 1));
//            *rend  = *rend % 2 + '0';
//        }
//        --rend;
//        --send;
//    }
//    while(rend > result.begin())
//    {
//        if(*rend == 2 + '0')
//        {
//            ++(*(rend - 1));
//            *rend  = *rend % 2 + '0';
//        }
//        --rend;
//    }
//    if(*rend == '0')
//    {
//        result.erase(result.begin());
//    }
//    return result;
//}
//int main()
//{
//    string a = "0";
//    string b = "0";
//    string sum = addBinary(a, b);
//    cout << sum << endl;
//    return 0;
////}
//#include <stdio.h>
//int main()
//{
//    int a[3][4] = {{1,3,5,7},
//                   {9,11,13,15},
//                   {17,19,21,23}};
//    int (*p) [4] = &a[0];
//    int q = &a[0];
//    return 0;
////}
//#include <stdio.h>
//int main()
//{
//    int a[2][2] = {1,2,3,4};
//    printf("%d\n", **(a + 1));
//    return 0;
//}
//#include <stdio.h>
//enum A
//{
//
//};
//int main()
///{
//    char c;
//    char *pc = &c;
//    char **ppc = &pc;
//
//    short s;
//    short *ps = &s;
//    short **pps = &ps;
//
//    int i;
//    int *pi = &i;
//    int **ppi = &pi;
//
//    double d;
//    double *pd = &d;
//    double **ppd = &pd;
//
//    float f;
//    float *pf = &f;
//    float **ppf = &pf;
//
////////////////无符号等基本数据类型
//
//    struct List l;
//    struct List *plist = &l;
//    struct List **pplist = &plist;
//
//    union All all;
//    union All *pall = &all;
//    union All **ppall = &pall;
//
////////////////enum、位段等自定义类型
//    int arr[5];
//    int (*parr) [5] = &arr;
//    int arr[5] = {1,2,3,4,5};
//    int *p = arr;
//    printf("%d\n", *(p+1));
//    char c = 0;
//    char *pc = &c;
//    printf("  pc = %p\n", pc);
//    printf("pc+1 = %p\n", pc + 1);
//    int i = 0;
//    int *pi = &i;
//    printf("  pi = %p\n", pi);
//    printf("pi+1 = %p\n", pi + 1);
//    double d = 0;
//    double *pd = &d;
//    printf("  pd = %p\n", pd);
//    printf("pd+1 = %p\n", pd + 1);
//    return 0;
//}
//int arr[5] = {1, 2, 3, 4, 5};
//    int a = 1;
//int *p = arr;
//printf("%d\n", *((int*)(char*)p + 1));
//    printf("%d\n", *((short*)p + 2));
//#include <stdio.h>
//int main()
//{
//    int a = 40000;
//    int *p = &a;
//    printf("%d\n", *p);
//    return 0;
//}
////
//printf("%d\n", *++p);
//printf("%d\n", ++*p);
//printf("%d\n", *p++);
//#include <stdio.h>
//int main()
//{
////   int arr[2][2] = {{1, 2}, {3, 4}};
////   int (*p)[2] = arr;
////   printf("%d\n", **(p + 1));
//    const char *p1 ="hello";
//    const char *const p2 = "world";
//   return 0;
//}
//#include <stdio.h>
//void FindNum(int (*ps)[5])
//{
//    for (int i = 0; i < 4; ++i)
//    {
//        int sum = 0;
//        int flag = 0;
//        for(int j = 0; j < 5; ++j)
//        {
//            if(*(*(ps + i) + j) <= 85)
//            {
//                flag = 1;
//            }
//            sum += *(*(ps + i) + j);
//        }
//        if(sum / 5 > 90 || flag == 0)
//        {
//            printf("学号：%d\n", i + 1);
//            printf("成绩为：");
//            for (int j = 0; j < 5; ++j)
//            {
//                printf("%d ", *(*(ps + i) + j));
//            }
//            printf("\n");
//        }
//    }
//}
//int main()
//{
//    int score[4][5] = {{90, 76, 89,67,88},
//                       {99,85,99,96,98},
//                       {100,100,98,98,78},
//                       {89,88,87,90,67}};
//    FindNum(score);
//    return 0;
//}
//#include <stdio.h>
//void example(char str[])
//{
//    printf("%d", sizeof(str));
//    return;
//}
//int main(){
//    char str[] = "hello world";
//    example(str);
//    return 0;
//}
//#include <iostream>
//int main()
//{
//    char str[10] = "lll";
//    *str = 's';
//    return 0;
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//int main()
//{
//    vector<int> v1{1,2,3,4,5};
//    vector<int> v2 = {1,2,3,4};
//    cout << v1.size() << endl;
//    cout << v1.capacity() << endl;
//    cout << sizeof(v1) << endl;
//
//    for(auto e : v1)
//    {
//        cout << e << ' ';
//    }
//    for(auto e : v2)
//    {
//        cout << e << ' ';
//    }
//    return 0;
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//vector<vector<int>> generate(int numRows)
//{
//    vector<vector<int>> row(numRows);
//    for(int i = 0; i < numRows; ++i)
//    {
//        if(i == 0)
//            row[i].push_back(1);
//        else
//        {
//            row[i].push_back(1);
//            row[i].push_back(1);
//        }
//        for(int j = 0; j < i + 1; ++j)
//        {
//            if(j != 0 && j != i)
//            {
//               int num = row[i - 1][j - 1] + row[i - 1][j];
//               row[i].insert(row[i].end()-1, num);
//            }
//        }
//    }
//    return row;
//}
//int main()
//{
//    generate(2);
//}
//#include "test.h"
//int main()
//{
//    bit::string s1("hello world");
//    bit::string s2(s1);
//    bit::string s3 = "ooooo";
//    s3 = s1;
//    return 0;
//}
/**
 *
#include "test.h"
namespace bit
{
    string::string(const string &s)
    {
        size_t len = strlen(s._str);
        _str = new char[len + 1];
        strcpy(_str, s._str);
    }
    string::string(const char *str)
    {
        assert(str);
        size_t len = strlen(str);
        _str = new char[len + 1];
        strcpy(_str, str);
    }
    string::~string()
    {
        delete []_str;
        _str = nullptr;
    }

    string& string::operator=(const string &s)
    {
        if(this != &s)
        {
            size_t len = strlen(s._str);
            _str = new char[len + 1];
            strcpy(_str, s._str);
        }
        return *this;
    }
}namespace bit
{
    class string
    {
    public:
        string(const char *str = "");
        string(const bit::string& s);
        bit::string& operator=(const bit::string& s);
        ~string();
    private:
        char *_str;
    };
}
 */
//#include <iostream>
//#include <vector>
//using namespace std;
//int main()
//{
//    vector<int> v1 = {1,2,3,4,5};
//    vector<int>::iterator it;
////    for(auto e : v1)
////    {
////        cout << e << ' ';
////    }
////    cout << endl;
////    it = v1.erase(v1.end() - 1);
////    int a = 2;
////
//////    for(auto e : v1)
//////    {
//////        cout << e << ' ';
//////    }
//////    cout << endl;
////    return 0;
//////}
//#include <iostream>
//#include <vector>
//using namespace std;
//void RecursiveFind(vector<string>& lets, vector<string>& ret, string& digits)
//{
//    int cut = ret.size();
//   for(int s = 0; s < digits.size() - 1; ++s)
//   {
//       if(digits[s] == '7' || digits[s] == '9')
//       {
//           cut = cut / 4;
//       }
//       else
//           cut = cut / 3;
//
//       int j = 0;
//       for (int i = 0; i < ret.size(); ++i)
//       {
//           int cur = cut;
//           while(cur--)
//           {
//               ret[i++] += lets[digits[s] - '0'][j];
//           }
//           --i;
//           ++j;
//           if(j == lets[digits[s] - '0'].size())
//               j = 0;
//       }
//   }
//
//    for (int i = 0; i < ret.size(); ++i)
//    {
//        for (int j = 0; j < lets[digits[digits.size()-1] - '0'].size(); ++j)
//        {
//            ret[i++] += lets[digits[digits.size()-1] - '0'][j];
//        }
//        --i;
//    }
//
//}
//vector<string> letterCombinations(string digits)
//{
//    //输入为空
//    vector<string> empty;
//    if(digits.size() == 0)
//        return empty;
//
//    //不为空
//    vector<string> letters = {"\0", "\0", "abc", "def", "ghi",
//                              "jkl", "mno", "pqrs", "tuv", "wxyz"};
//
//    string::iterator begin = digits.begin();
//    int capa = 1;
//    while(begin != digits.end())
//    {
//        if(*begin == '7' || *begin == '9')
//        {
//            capa *= 4;
//        }
//        else
//            capa *= 3;
//        ++begin;
//    }
//    vector<string> ret(capa);
//    RecursiveFind(letters, ret, digits);
//    return ret;
//}
//int main()
//{
//    vector<string> vs = letterCombinations("738");
//    return 0;
//}
#include <vector>
//#include <iostream>
using namespace std;
//void duplicateZeros(vector<int>& arr)
//{
//    auto begin = arr.begin();
//
//    while(begin != arr.end())
//    {
//        auto cur = begin + 1;
//        if(*begin == 0)
//        {
//            arr.insert(cur, 0);
//        }
//        ++begin;
//    }
//}
//void duplicateZeros(vector<int>& arr)
//{
//    auto begin = arr.begin();
//    auto end = arr.end();
//    int i = 0;
//    while(begin < end)
//    {
//        if(*begin == 0)
//        {
//            auto cur = begin + 1;
//            begin = arr.insert(cur, 0);
//            ++i;
//        }
//        ++begin;
//    }
//    arr.resize(arr.size() - i);
////}
//#include <iostream>
//class A
//{
////public:
////    int fun1();
////private:
////    int _a;
////    static int b;
////};
////int main()
////{
////    cout << sizeof (A) << endl;
////    return 0;
////}
//#include <stdio.h>
//typedef struct student
//{
//    long number;
//    char name[50];
//    float score[3];
//    float average;
//    int rank;
//}ST;
//typedef struct Num
//{
//    ST stdnum[5];
//    int num;
//}Num;
//
//void ScanfPessage(Num *psa)
//{
//    for(int i = 0; i < 5; ++i)
//    {
//        scanf("%ld %s", &psa->stdnum[i].number, psa->stdnum[i].name);
//        for(int j = 0; j < 3; ++j)
//        {
//            scanf("%f", &psa->stdnum[i].score[j]);
//        }
//    }
//}
//void Average(Num *psa)
//{
//    for(int i = 0; i < 5; ++i)
//    {
//        float sum = 0;
//        for (int j = 0; j < 3; ++j)
//        {
//            sum += psa->stdnum[i].score[j];
//        }
//        psa->stdnum[i].average = sum / 3;
//    }
//}
//void Rank(Num *psa)
//{
//    for (int i = 0; i < 5; ++i)
//    {
//        float everyage = psa->stdnum[i].average;
//        int n = i + 1;
//        for(int j = i + 1; j < 5; ++j)
//        {
//            float otherage = psa->stdnum[j].average;
//            if(everyage < otherage)
//            {
//                --n;
//            }
//        }
//        psa->stdnum[i].rank = n;
//    }
//
//}
//void Print(Num *psa)
//{
//    printf("Number: Name:   score:  Average:    rank:\n");
//    for(int i = 0; i < 5; ++i)
//    {
//        printf("%-9ld %-10s", psa->stdnum[i].number, psa->stdnum[i].name);
//        for(int j = 0; j < 3; ++j)
//        {
//            scanf("%-5.1f", psa->stdnum[i].score[j]);
//        }
//        printf("%-10.1f%-d\n", psa->stdnum[i].average, psa->stdnum[i].rank);
//    }
//}
//int main()
//{
//    Num pessage;
//    ScanfPessage(&pessage);
//    Average(&pessage);
//    Rank(&pessage);
//    Print(&pessage);
////    return 0;
////}
//#include "test.h"
//void Test3()
//{
//    wyd::vector<int> v1{1,2,3,4,5};
//    wyd::vector<int> v2(v1);
//    for(auto e : v1)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//    for(auto e : v2)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//}
//int main()
//{
//    // Test1();
//    // Test2();
//    Test3();
//    return 0;
//}
/**
 * namespace wyd
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

        ////////// Construct And Destroy ///////////
        vector()
                : _start(nullptr)
                , _finish(nullptr)
                , _end_of_storage(nullptr)
        {}
        vector(const T& v)
        {
            resever(sizeof(len));
            memcpy(_start, v, sizeof(T)*len);
            _finish = _start + len;
        }
        vector(const vector<T>& v)
        {
            resever(v.capacity());
            memcpy(_start, v._start, sizeof(int)*v.size());
            _finish = _start + v.size();
        }
        // T& operator=()
        // {
//
        // }
        ~vector()
        {
            delete []_start;
            _start = _finish = _end_of_storage = nullptr;
        }

        ////////// iterator ///////////
        iterator begin()
        {
            return _start;
        }
        const_iterator begin() const
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        const_iterator end() const
        {
            return _finish;
        }

        /////////// Size And Capacity //////////////
        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity() const
        {
            return _end_of_storage - _start;
        }
        void resever(size_t n)
        {
            if(n > capacity())
            {
                T* new_start = new T[n];
                size_t data = size();
                memcpy(new_start, _start, sizeof(int)*size());
                if(_start != nullptr)
                {
                    delete []_start;
                }
                _start = new_start;
                _finish = _start + data;
                _end_of_storage = _start + n;
            }
        }
        void resize(size_t n, T& data)
        {
            if(n > size())
            {
                if(n > capacity())
                    resever(n);

                memset(_finish, data, n-size());
            }

            _finish = _start + n;
        }
        ///////////// Insert And Delete ////////////////
        void push_back(const T& num)
        {
            if(_finish == _end_of_storage)
            {
                size_t new_capacity = capacity() == 0 ? 4 : 2*capacity();
                resever(new_capacity);
            }
            *_finish = num;
            ++_finish;
        }
        T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }


    private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
    };
}
//
// */
//#include "test.h"
//void Test1()
//{
//    wyd::vector<int> v1;
//    v1.push_back(1);
//    v1.push_back(2);
//    v1.push_back(3);
//    v1.push_back(4);
//    v1.push_back(4);
//    v1.push_back(4);
//    v1.push_back(4);
//    v1.push_back(4);
//    v1.push_back(4);
//    wyd::vector<int> v2(v1);
//    v1.push_back(40000);
//    v2 = v1;
//    for(auto e : v1)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//    for(auto e : v2)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
////    wyd::vector<int>::iterator it = v1.begin();
////    while(it != v1.end())
////    {
////        cout << *(it++) << ' ';
////    }
////    cout << endl;
//}
//void Test2()
//{
//    wyd::vector<int> v1;
//    v1.push_back(2);
//    v1.push_back(23);
//    v1.push_back(24);
//    v1.push_back(25);
//    v1.push_back(26);
//    for(int i = 0; i < v1.size(); ++i)
//    {
//        cout << v1[i] << ' ';
//    }
//    cout << endl;
//}
//void Test3()
//{
//    wyd::vector<int> v1(10, 2);
//    wyd::vector<int> v2(v1);
//    for(auto e : v1)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//    for(auto e : v2)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//}
//int main()
//{
//     Test1();
//    // Test2();
////    Test3();
//    return 0;
//}
/**
 * #include <iostream>
#include <assert.h>
using namespace std;
namespace wyd
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

        ////////// Construct And Destroy ///////////
        vector()
                : _start(nullptr)
                , _finish(nullptr)
                , _end_of_storage(nullptr)
        {}
        vector(const vector<T>& v)
        {
            _start = new T[v.capacity()];
            _end_of_storage = _start + v.capacity();
            _finish = _start + v.size();
            memcpy(_start, v._start, sizeof(T)*v.size());
        }
        vector(size_t n, const T& value = T())
        {
            _start = new T[n];
            _end_of_storage = _start + n;
            _finish = _start + n;
            memset(_start, value, sizeof(T) * n);
        }
        vector<T>& operator=(const vector<T>& v)
        {
            if(this != &v)
            {
                _start = new T[v.capacity()];
                _end_of_storage = _start + v.capacity();
                _finish = _start + v.size();
                memcpy(_start, v._start, sizeof(T)*v.size());
            }
            return *this;
        }
        ~vector()
        {
            delete []_start;
            _start = _finish = _end_of_storage = nullptr;
        }

        ////////// iterator ///////////
        iterator begin()
        {
            return _start;
        }
        const_iterator begin() const
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        const_iterator end() const
        {
            return _finish;
        }

        /////////// Size And Capacity //////////////
        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity() const
        {
            return _end_of_storage - _start;
        }
        void resever(size_t n)
        {
            if(n > capacity())
            {
                T* new_start = new T[n];
                size_t data = size();
                memcpy(new_start, _start, sizeof(int)*size());
                if(_start != nullptr)
                {
                    delete []_start;
                }
                _start = new_start;
                _finish = _start + data;
                _end_of_storage = _start + n;
            }
        }
        void resize(size_t n, const T& data = T())
        {
            if(n > size())
            {
                if(n > capacity())
                    resever(n);

                memset(_finish, data, sizeof(T) * ( n - size() ) );
            }

            _finish = _start + n;
        }
        ///////////// Insert And Delete ////////////////
        void push_back(const T& num)
        {
            if(_finish == _end_of_storage)
            {
                size_t new_capacity = capacity() == 0 ? 4 : 2*capacity();
                resever(new_capacity);
            }
            *_finish = num;
            ++_finish;
        }

        void pop_back()
        {
            assert(size() >= 0);
            --_finish;
        }

        /////////////// [] ///////////////
        T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }
        const T& operator[](size_t pos) const
        {
            assert(pos < size());
            return _start[pos];
        }
    private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
//    };
//}
// */
//#include <iostream>
//using namespace std;
//vector<int> singleNumber(vector<int>& nums)
//{
//    int max = nums[0];
//    for(int i = 1; i < nums.size(); ++i)
//    {
//        if(max < nums[i])
//        {
//            max = nums[i];
//        }
//    }
//
//    int arr[max];
//    memset(arr, 0, max*sizeof(int));
//    for(int i = 0; i < nums.size(); ++i)
//    {
//        ++arr[nums[i]];
//    }
//
//    vector<int> v;
//    for(int i = 0; i < max; ++i)
//    {
//        if(arr[i] == 1)
//        {
//            v.push_back(i);
//        }
//    }
//
//    return v;
//}
//int main()
//{
//    vector<int> v1 = {1,2,2,3,3,4};
//    vector<int> re = singleNumber(v1);
//    for(auto e : re)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//    return 0;
//}















